#pragma once
#include "TreeNode.h"
#include <vector>
using std::vector;

template <class T>
class BinaryTree
{
public:
	enum CHILD_POSITION
	{
		POSITION_LEFT = 0,
		POSITION_RIGHT = 1
	};
	typedef void(*pSearchFunc)(TreeNode<T>* node);

	BinaryTree(void);
	virtual ~BinaryTree(void);

	void createTree(vector<T*>* pVecData);
	void appendNode(TreeNode<T>* newNode, TreeNode<T>* whichNode, CHILD_POSITION position);

	void inOrder(pSearchFunc,TreeNode<T>* pNode);
	void postOrder(pSearchFunc,TreeNode<T>* pNode);

	TreeNode<T>* root() {return _root;}
private:
	TreeNode<T>* _root;
};

template <class T>
BinaryTree<T>::BinaryTree(void)
{
	_root = NULL;
}

template <class T>
BinaryTree<T>::~BinaryTree(void)
{
	// TODO
	//TreeNode<T>* pNode = _root;
	//if (pNode != NULL)
	//{
	//	if (pNode->_rChild != NULL)
	//	{
	//		postOrder(pNode->_rChild);
	//	}
	//	if (pNode->_lChild != NULL)
	//	{
	//		postOrder(pNode->_lChild);
	//	}
	//	delete pNode;
	//}
}

template <class T>
void BinaryTree<T>::createTree(vector<T*>* pVecData)
{
	TreeNode<T>* temp = NULL;
	vector<T*>::iterator iter;
	for (iter=pVecData->begin();iter!=pVecData->end();iter++)
	{
		TreeNode<T>* node = new TreeNode<T>(*iter);
		node->_lChild=NULL;
		node->_rChild=NULL;
		if (_root==NULL)
		{
			_root = node;
			continue;
		} else {
			temp = _root;
		}

		while (true)
		{
			if (*(*iter) < *(temp->get()))
			{
				if (temp->_lChild==NULL)
				{
					temp->_lChild = node;
					break;
				} else {
					temp = temp->_lChild;
				}
			} else {
				if(temp->_rChild==NULL)
				{
					temp->_rChild = node;
					break;
				} else {
					temp = temp->_rChild;
				}
			}
		}
	}	
}

template <class T>
void BinaryTree<T>::appendNode(TreeNode<T>* newNode, TreeNode<T>* whichNode, CHILD_POSITION position)
{
	if (newNode == NULL)
	{
		return;
	}
	if (whichNode == NULL)
	{
		_root = newNode;
		return;
	}

	newNode->_parent = whichNode;
	newNode->_lChild = NULL;
	newNode->_rChild = NULL;
	switch (position)
	{
	case POSITION_LEFT:
		// the leaf of the node must be empty
		if (whichNode->_lChild!=NULL)
		{
			return;
		}
		whichNode->_lChild = newNode;
		break;
	case POSITION_RIGHT:
		// the leaf of the node must be empty
		if (whichNode->_rChild!=NULL)
		{
			return;
		}
		whichNode->_rChild = newNode;
		break;
	default:
		return;
	}
}

template <class T>
void BinaryTree<T>::inOrder(pSearchFunc func, TreeNode<T>* pNode)
{
	if (pNode != NULL)
	{
		if (pNode->_lChild != NULL)
		{
			inOrder(func,pNode->_lChild);
		}
		func(pNode);
		if (pNode->_rChild != NULL)
		{
			inOrder(func,pNode->_rChild);
		}
	}
}

template <class T>
void BinaryTree<T>::postOrder(pSearchFunc func,TreeNode<T>* pNode)
{
	if (pNode != NULL)
	{
		if (pNode->_rChild != NULL)
		{
			postOrder(func,pNode->_rChild);
		}
		func(pNode);
		if (pNode->_lChild != NULL)
		{
			postOrder(func,pNode->_lChild);
		}
	}
}